package com.wc.acwing.基础算法.位运算.a的b次方;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/1/16 0:51
 * @description a^b
 * https://www.acwing.com/problem/content/description/91/
 */
public class Main {
    static long a, b, p;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextLong();
        b = sc.nextLong();
        p = sc.nextLong();
        System.out.println(qPow(a, b, p));
    }

    static long qPow(long a, long b, long p) {
        // 0的任何次方都是0
        if (a == 0) {
            return 0;
        }
        long res = 1;
        while (b > 0) {
            // 判断b是否为奇数
            if ((b & 1) == 1) {
                res = res * a % p;
            }
            a = a * a % p;
            b >>= 1;
        }
        return res % p;
    }
}
